、#include<stdio.h>
#include<iostream>
using namespace std;
#define Status int
#define OK 1
#define ERROR 0
#define TRUE true
#define OVERFLOW false
//树型结构(非线性结构) 结点之间有分支，具有层次关系
// 树(Tree)是n(n>=0)个结点的有限集 

//二叉树 BinaryTree
//二叉树的基本操作： 
//1. CreateBiTree(&T, definition) 按definition构造二叉树T 
//2. PreOrderTraverse(T) 先序遍历T 
//3. InOrderTraverse(T)  中序遍历T
//4. PostOrderTraverse(T) 后序遍历T,对每个结点访问一次 

//二叉树的性质
//满二叉树一定是完全二叉树 
//完全二叉树不一定是满二叉树


//二叉树的存储结构：顺序存储结构，链式存储结构(二叉链表、三叉链表) 

//二叉树的顺序存储：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 
#define MAXSIZE 100
#define TElemType char //元素类型 
typedef TElemType SqBiTree[MAXSIZE];
//SqBiTree bt; //定义一个二叉树变量 


//二叉链表存储结构 
typedef struct BiNode{
	TElemType data;
	struct BiNode *lchild, *rchild;  //左右孩子指针 
}BiTNode, *BiTree; 


//三叉链表存储结构 
typedef struct TriTNode{
	TElemType data;
	struct TriTNode *lchild, *parent, *rchild;
}TriTNode, *TriTree; 


//遍历二叉树
//遍历的定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次(又称周游) 
//遍历的目的：得到树中所有结点的一个线性排列
//遍历的用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心

//L：遍历左子树  D:访问根结点  R：遍历右子树
//规定先左后右，则有 DLR先(根)序遍历、LDR中(根)序遍历、LRD后(根)序遍历 

 
void visit(BiTree T){
	printf("%c ", T->data);//count<<T->data<<"\t";
}

//先序遍历：
//		若二叉树为空，则空操作;
//		若二叉树非空，访问根结点(D)，前序遍历左子树(L)，前序遍历右子树(R) 
Status PreOrderTraverse(BiTree T){
	if(T == NULL) return OK;//空二叉树
	else {
		visit(T); //访问根结点 
		PreOrderTraverse(T->lchild);//遍历递归左子树
		PreOrderTraverse(T->rchild);//遍历递归右子树 
	} 
}

//中序遍历：
//		 若二叉树为空，则空操作;
//		 否则：中序遍历左子树(L), 访问根结点(D), 中序遍历右子树(R) 
Status InOrderTraverse(BiTree T){
	if(T == NULL) return OK;//空二叉数
	else{
		InOrderTraverse(T->lchild);
		visit(T);
		InOrderTraverse(T->rchild);
	} 
}

//后序遍历：
//		若二叉树为空，则空操作;
//		否则：后序遍历左子树(L), 后序遍历右子树(R), 访问根结点(D) 
Status PostOrderTraverse(BiTree T){
	if(T == NULL) return OK;
	else {
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		visit(T);
	}
}

//遍历算法分析：
//时间效率：O(n)  每个结点只能访问一次
//空间效率: O(n)  栈占用的最大辅助空间 




//中序遍历的非递归算法
//		关键：在中序遍历过的某结点的整个左子树之后，如何找到该结点的根和右子树
//基本思想：(1)建立一个栈 (2)根结点进栈，遍历左子树  (3)根结点出栈，输出根结点，遍历右子树 
//伪码如下： 
/*
Status InOrderTraverse(BiTree T){
	BiTree p;
	InitStack(S);
	p = T;
	while(p || StackEmpty(S)){
		if(p){
			Push(S, p);
			p = p->lchild;
		} else{
			BiTree(q);
			Pop(S, q);
			printf("%c", q->data);
			p = q->rchild;	
		}//while
	}
	return OK;
}
*/


//二叉树的层次遍历：使用一个队列 
//1. 将根结点入队；
//2. 队不空时循环：从队列出列一个结点*p，访问它;
//		若它有左孩子节点，将左孩子节点进队；
//		若它有右孩子结点，将右孩子结点进队。
/*
#define BTNode  BiTNode
#define MAXQSIZE 100
typedef struct{
	BTNode data[MAXQSIZE]; //存放队中元素
	int front, rear;  //队头和队尾指针 
} SqQueue; //顺序循环队列类型 
//二叉树的层次遍历算法如下：
void LevelOrder(BiTNode *&b){
	BiTNode *p;  
	SqQueue *qu;  
	InitSqQueue(qu); //初始化队列 
	EnQueue(qu, b);  //根结点指针进入队列 
	while(!QueueEmpty(qu)){  //队不为空,则循环 
		DeQueue(qu, p);  //出队结点p 
		cout<<p->data;  //访问结点p 
		if(p->lchild) EnQueue(qu, p->lchild); //有左孩子时将其入队 
		if(p->rchild) EnQueue(qu, p->rchild); //有右孩子时将其进队 
	}
} 
*/





//二叉树遍历算法的应用----二叉树的建立(算法5.3)
//按先序遍历序列建立二叉树的二叉链表 
//先序遍历输入某二叉树：ABC##DE#G##F###    #表示空字符
Status CreateBiTree(BiTree &T){
	char ch;
	cin>>ch; //scanf("%c", &ch); 
	if(ch == '#') T = NULL;
	else {
		if( !(T = new BiTNode) ) // T = (BiTNode *)malloc(sizeof(BiTNode))
			exit(OVERFLOW);
		T->data = ch; //生成根节点
		CreateBiTree(T->lchild); //构造左子树
		CreateBiTree(T->rchild); //构造右子树 
	}
	return OK;
} //先序递归构建二叉树 



//二叉树遍历算法的应用--复制二叉树(算法5.4)
//如果是空树，递归结束；
//否则，申请新结点空间，复制根结点：递归复制左子树，递归复制右子树
int Copy(BiTree T, BiTree &NewT){
	if(T == NULL){ 
		NewT = NULL;
		return 0; //如果是空树，返回0 
	} 
	else{
		NewT = new BiTNode;
		NewT->data = T->data;
		Copy(T->lchild, NewT->lchild);
		Copy(T->rchild, NewT->rchild);
	}
} 


//二叉树遍历算法的应用----计算二叉树的深度(算法5.5)
//如果是空树，则深度为0
//否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者+1
int Depth(BiTree T){
	if(!T) return 0; //如果是空树返回0 
	else{
		int m = Depth(T->lchild);
		int n = Depth(T->rchild);
		if(m>n) return m+1;
		else return n+1;
	}	
}

//二叉树遍历算法的应用----计算二叉树结点总数(算法5.6)
//如果是空树，则结点个数为0;
//否则，结点个数为 左子树的结点个数 + 右子树的结点个数 + 1
int NodeCount(BiTree T){
	if(!T) return 0;
	else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
} 



//二叉树遍历算法的应用----计算二叉树叶子结点数
//如果是空树，则叶子结点个数为0
//否则，为左子树的叶子结点个数 + 右子树的结点个数
int LeafCount(BiTree T){
	if(T == NULL) return 0; //如果是空树返回0
	if(T->lchild == NULL && T->rchild == NULL) return 1;
	else return LeafCount(T->lchild) + LeafCount(T->rchild);
}


int main(void){
	BiTree T;
	printf("先序递归创建二叉树...\n");
	//ABC##DE#G##F###
	CreateBiTree(*&T);
	puts("二叉树创建完毕，先序遍历如下：");
	PreOrderTraverse(T);
	BiTree NewT;
	Copy(T, *&NewT);
	printf("\n复制T到NewT中，遍历NewT如下：\n");
	PreOrderTraverse(NewT);
	int depth_T = Depth(T);
	int depth_NewT = Depth(NewT);
	printf("\ndepth_T = %d, depth_NewT = %d\n", depth_T, depth_NewT); 
	int T_nodes = NodeCount(T);
	int NewT_nodes = NodeCount(NewT);
	printf("T_nodes = %d, NewT_nodes = %d\n", T_nodes, NewT_nodes);
	int leafs_T = LeafCount(T);
	int leafs_NewT = LeafCount(T);
	printf("leafs_T = %d leafs_NewT = %d\n", leafs_T, leafs_NewT);
	return 0;
}